package sort;

import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.Random;

/**
 * 归并排序：分治 + 递归
 */
public class TestMergeSort {

    @Test
    public void test01() {
        // 1. 准备样本
        int[] arr = new int[10];
        Random random = new Random();
        for (int i = 0; i < 10; i++) {
            arr[i] = random.nextInt(100);
        }
        System.out.println(Arrays.toString(arr));

        // 2. 归并排序
        mergeSort(arr, 0, 9);

        // 3. 检验结果
        System.out.println(Arrays.toString(arr));
    }

    /**
     * L：左边界
     * R：右边界
     */
    public void mergeSort(int[] arr, int L, int R) {
        // 1. base case
        if (L >= R) {
            return;
        }

        // 2. recursion case
        int len = R - L + 1;  // 元素个数
        int mid = L + ((R - L) >> 1);  // 中间值
        int[] help = new int[len];  // 辅助数组
        int p1 = L;  // 左区遍历指针
        int p2 = mid + 1;  // 右区遍历指针
        int i = 0;  // help索引

        // 先分治，再递归
        mergeSort(arr, L, mid);
        mergeSort(arr, mid + 1, R);

        while (p1 <= mid && p2 <= R) {  // 当 p1 p2 都不越界
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }

        // 剩余元素放入 help
        while (p1 <= mid) {  // 当 p1 不越界
            help[i++] = arr[p1++];
        }
        while (p2 <= R) {  // 当 p2 不越界
            help[i++] = arr[p2++];
        }

        // help 覆盖 arr
        System.arraycopy(help, 0, arr, L, len);
    }
}
